package leetcode;


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

/**
 * create by duanx 2022/2/7
 *
 * @classname: Test3
 * @author: duanx
 * @date: 2022/2/7 9:22
 **/
public class Test15 {
    /**
     * 定义方向
     */
    public static int[][] directions = {
            {0, 1},
            {1, 0},
            {-1, 0},
            {0, -1}
    };
    /**
     * 路径记录
     */
    private static Stack<int[]> path;
    /**
     * 路径
     */
    private static ArrayList<int[]> minPath;
    /**
     * 迷宫
     */
    private static int[][] matrix;
    /**
     * 访问过的
     */
    private static boolean[][] visited;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1;
        while ((str1 = br.readLine()) != null) {
            String[] arr = str1.split(" ");
            int rows = Integer.parseInt(arr[0]);
            int cols = Integer.parseInt(arr[1]);
            path = new Stack<>();
            minPath = null;
            matrix = new int[rows][cols];
            visited = new boolean[rows][cols];
            // 组装迷宫 二维数组matrix
            for (int i = 0; i < rows; i++) {
                String[] str2 = br.readLine().split(" ");
                for (int j = 0; j < cols; j++) {
                    matrix[i][j] = Integer.parseInt(str2[j]);
                }
            }
            //广度优先遍历
            dfs(0, 0);

            //输出路径
            StringBuilder sb = new StringBuilder();
            for (int[] res : minPath) {
                sb.append('(').append(res[0]).append(',').append(res[1]).append(")\n");
            }
            System.out.print(sb);
        }
    }

    public static void dfs(int i, int j) {
        //边界条件
        if (i > matrix.length - 1 || i < 0 || j > matrix[0].length - 1 || j < 0 || visited[i][j] || matrix[i][j] == 1 || (minPath != null && path.size() >= minPath.size())) {
            return;
        }
        if (i == matrix.length - 1 && j == matrix[0].length - 1) {
            path.add(new int[]{i, j});
            minPath = new ArrayList<>(path);
            path.pop();
            return;
        }
        path.add(new int[]{i, j});
        visited[i][j] = true;
        for (int[] direction : directions) {
            dfs(i + direction[0], j + direction[1]);
        }
        visited[i][j] = false;
        path.pop();
    }

    /**
     * 迷宫找路
     * @param maze 迷宫二维矩阵
     * @param i 起点
     * @param j 终点
     */
    public static void findWay(int[][] maze ,int i,int j){
        if ( maze[maze.length-1][maze[0].length-1] == 2){
            return;
        }

    }
}
